﻿/*
** Xin YUAN, 2021, BSD (2)
*/

/*
Comparison Functions

Author: Gao Chengxiang
*/

////////////////////////////////////////////////////////////////////////////////
#ifndef __CTL_DIFF_H__
#define __CTL_DIFF_H__
////////////////////////////////////////////////////////////////////////////////

#ifndef __CTL_DEF_H__
	#error diff.h requires def.h to be included first.
#endif

////////////////////////////////////////////////////////////////////////////////
namespace CTL {
////////////////////////////////////////////////////////////////////////////////

//------------------------------------------------------------------------------
// myers algorithm

// point
struct myers_point
{
	int32_t x, y;
};

//find middle point from start to end in edit graph (a, b)
template <class TIterator, class TCompareTrait = DefaultCompareTrait<typename TIterator::ValueType>>
inline void myers_find_middle(const typename IteratorTraits<TIterator>::ValueType* a, const typename IteratorTraits<TIterator>::ValueType* b,
							const myers_point& start, const myers_point& end,
							typename ArrayTraits<int32_t>::ArrayType& arrForward, typename ArrayTraits<int32_t>::ArrayType& arrBackward,
							myers_point& pt) noexcept
{
	/*
	start 1 2 ... n
	1
	2
	...
	m             end
	*/
	int32_t n = end.x - start.x;  //x
	int32_t m = end.y - start.y;  //y

	//initialize
	for(int32_t i = 0; i <= n + m; ++ i)
		ArrayTraits<int32_t>::GetAt(arrForward, i) = -1;
	ArrayTraits<int32_t>::GetAt(arrForward, m + 1) = 0;
	for(int32_t i = 0; i <= n + m; ++ i)
		ArrayTraits<int32_t>::GetAt(arrBackward, i) = -1;
	ArrayTraits<int32_t>::GetAt(arrBackward, n - 1) = n;

	for(int32_t d = 0; d <= (n + m + 1) / 2; d++) {
		//forward
		for(int32_t k = -m + ((d^m)&1), kInv = k + m; k <= n; k += 2, kInv = k + m) {
			int32_t x, y;
			if((kInv == 0 || ArrayTraits<int32_t>::GetAt(arrForward, kInv - 1) < 0) && (kInv == m+n || ArrayTraits<int32_t>::GetAt(arrForward, kInv + 1) < 0)) {
				continue;
			}
			else if(kInv == 0 || ArrayTraits<int32_t>::GetAt(arrForward, kInv - 1) < 0 || (kInv != n + m && ArrayTraits<int32_t>::GetAt(arrForward, kInv + 1) >= 0 && ArrayTraits<int32_t>::GetAt(arrForward, kInv - 1) < ArrayTraits<int32_t>::GetAt(arrForward, kInv + 1))) {
				//now: move from top (k+1)
				x = ArrayTraits<int32_t>::GetAt(arrForward, kInv + 1);
				y = x - k;
			}
			else {
				//now: move from left (k-1)
				x = ArrayTraits<int32_t>::GetAt(arrForward, kInv - 1) + 1;
				y = x - k;
			}
			if(x > n || y > m || x < 0 || y < 0)
				continue;
			int32_t endx = x, endy = y;
			while(endx < n && endy < m && TCompareTrait::IsEQ(a[endx + start.x], b[endy + start.y]))
				endx++, endy++;
			ArrayTraits<int32_t>::GetAt(arrForward, kInv) = endx;
			if(ArrayTraits<int32_t>::GetAt(arrForward, kInv) >= 0 && ArrayTraits<int32_t>::GetAt(arrBackward, kInv) >= 0 && ArrayTraits<int32_t>::GetAt(arrForward, kInv) >= ArrayTraits<int32_t>::GetAt(arrBackward, kInv)) {
				pt.x = x + start.x;
				pt.y = y + start.y;
				return ;
			}
		}

		//backward
		for(int32_t k = -m + ((d^n)&1), kInv = k + m; k <= n; k += 2, kInv = k + m) {
			int32_t x, y;
			if((kInv == 0 || ArrayTraits<int32_t>::GetAt(arrBackward, kInv - 1) < 0) && (kInv == m+n || ArrayTraits<int32_t>::GetAt(arrBackward, kInv + 1) < 0)) {
				continue;
			}
			else if(kInv == m + n || ArrayTraits<int32_t>::GetAt(arrBackward, kInv + 1) < 0 || (kInv != 0 && ArrayTraits<int32_t>::GetAt(arrBackward, kInv - 1) >= 0 && ArrayTraits<int32_t>::GetAt(arrBackward, kInv - 1) < ArrayTraits<int32_t>::GetAt(arrBackward, kInv + 1))) {
				//move from bottom
				x = ArrayTraits<int32_t>::GetAt(arrBackward, kInv - 1);
				y = x - k;
			}
			else {
				//move from right
				x = ArrayTraits<int32_t>::GetAt(arrBackward, kInv + 1) - 1;
				y = x - k;
			}
			if(x > n || y > m || x < 0 || y < 0)
				continue;
			while(x > 0 && y > 0 && TCompareTrait::IsEQ(a[x - 1 + start.x], b[y - 1 + start.y]))
				x--, y--;
			ArrayTraits<int32_t>::GetAt(arrBackward, kInv) = x;
			if(ArrayTraits<int32_t>::GetAt(arrForward, kInv) >= 0 && ArrayTraits<int32_t>::GetAt(arrBackward, kInv) >= 0 && ArrayTraits<int32_t>::GetAt(arrForward, kInv) >= ArrayTraits<int32_t>::GetAt(arrBackward, kInv)) {
				pt.x = x + start.x;
				pt.y = y + start.y;
				return ;
			}
		}
	}
	pt = end;
}

//Longest common sequence
struct LcsItem
{
	int32_t iStart1;  //based 0
	int32_t iEnd1;
	int32_t iStart2;  //based 0
	int32_t iEnd2;
};

//myers algorithm

template <class TIterator, class TCompareTrait = DefaultCompareTrait<typename TIterator::ValueType>>
inline void MyersDiff(const TIterator& a_begin, const TIterator& a_end,
					const TIterator& b_begin, const TIterator& b_end,
					typename ArrayTraits<LcsItem>::ArrayType& arrLCS)
{
	//length
	intptr_t a_size = IteratorTraits<TIterator>::CalcDistance(a_begin, a_end);
	intptr_t b_size = IteratorTraits<TIterator>::CalcDistance(b_begin, b_end);
	assert( a_size >= 0 && b_size >= 0 );
	if( a_size > NumericTraits<int32_t>::MaxValue
		|| b_size > NumericTraits<int32_t>::MaxValue )
		ExceptionTraits::ThrowOverflow();  //throw
	int32_t n = (int32_t)a_size;
	int32_t m = (int32_t)b_size;

	//V[k]: forward & backward
	ArrayTraits<int32_t>::ArrayType arrForward;
	ArrayTraits<int32_t>::ArrayType arrBackward;
	{
		//n+m+2
		int32_t count = ArithmeticTraits<int32_t>::AddThrow(n, m);  //may throw
		count = ArithmeticTraits<int32_t>::AddThrow(count, (int32_t)2);  //may throw
		ArrayTraits<int32_t>::SetSize(arrForward, count);  //may throw
		ArrayTraits<int32_t>::SetSize(arrBackward, count);  //may throw
	}

	//result
	ArrayTraits<LcsItem>::Clear(arrLCS);

	//add all or delete all
	if( n == 0 || m == 0 )
		return ;

	//division stack
	ArrayTraits<myers_point>::ArrayType arrSearchStack;
	//edit path
	ArrayTraits<myers_point>::ArrayType arrEditPath;

	//initialize
	myers_point start{0, 0};
	myers_point end{n, m};
	myers_point middle;

	//loop
	do {
		//same sequence at beginning
		while(start.x != end.x && start.y != end.y
			&& TCompareTrait::IsEQ(*(&(IteratorTraits<TIterator>::Get(a_begin))+start.x), *(&(IteratorTraits<TIterator>::Get(b_begin))+start.y))
			) {
			start.x++;
			start.y++;
			ArrayTraits<myers_point>::Append(start, arrEditPath);  //based 1, may throw
		}

		//current n < current m
		while(start.x == end.x && start.y != end.y) {
			start.y++;
			ArrayTraits<myers_point>::Append(start, arrEditPath);  //may throw
		}
		//current n > current m
		while(start.x != end.x && start.y == end.y) {
			start.x++;
			ArrayTraits<myers_point>::Append(start, arrEditPath);  //may throw
		}

		//search
		if(start.x != end.x || start.y != end.y) {
			myers_find_middle<TIterator, TCompareTrait>(&(IteratorTraits<TIterator>::Get(a_begin)), &(IteratorTraits<TIterator>::Get(b_begin)), start, end, arrForward, arrBackward, middle);
			ArrayTraits<myers_point>::Append(end, arrSearchStack);  //may throw
			end = middle;
		}
		else {
			uintptr_t stack_size = ArrayTraits<myers_point>::GetSize(arrSearchStack);
			if(stack_size != 0) {
				end = ArrayTraits<myers_point>::GetAt(arrSearchStack, stack_size - 1);
				ArrayTraits<myers_point>::RemoveAt(arrSearchStack, stack_size - 1);
			}
		}
	} while(start.x != end.x || start.y != end.y || ArrayTraits<myers_point>::GetSize(arrSearchStack) != 0);

	//to LCS
	start.x = start.y = 0;
	uintptr_t path_size = ArrayTraits<myers_point>::GetSize(arrEditPath);
	for( uintptr_t i = 0; i < path_size; i ++ ) {
		const myers_point& it(ArrayTraits<myers_point>::GetAt(arrEditPath, i));
		//the same
		if(it.x == start.x + 1 && it.y == start.y + 1) {
			uintptr_t lcs_size = ArrayTraits<LcsItem>::GetSize(arrLCS);
			if(lcs_size != 0) {
				LcsItem& item(ArrayTraits<LcsItem>::GetAt(arrLCS, lcs_size - 1));
				if(item.iEnd1 + 1 == start.x && item.iEnd2 + 1 == start.y) {
					item.iEnd1 = start.x;
					item.iEnd2 = start.y;
					start = it;
					continue;
				}
			}
			LcsItem item;
			item.iStart1 = item.iEnd1 = start.x;
			item.iStart2 = item.iEnd2 = start.y;
			ArrayTraits<LcsItem>::Append(item, arrLCS);  //may throw
		}
		else {
			assert( (it.x == start.x && it.y == start.y + 1) // add start.y
					|| (it.x == start.x + 1 && it.y == start.y) // delete start.x
				);
		}
		start = it;
	}
}

//Edit types
/*! \brief An enumeration for text comparison result types.

An enumeration for text comparison result types.
*/
enum {
	Diff_Add = 0,  //!< add
	Diff_Delete,   //!< delete
	Diff_Revise    //!< change
};

//Diff item
/*! \brief A structure for text comparison result item.

A structure for text comparison result item.
*/
struct DiffItem
{
	int32_t iType;    //!< type, see Diff_*.
	int32_t iStart1;  //!< the start offset of container 1, based 0.
	int32_t iEnd1;    //!< the end offset of container 1 (mute element).
	int32_t iStart2;  //!< the start offset of container 2, based 0.
	int32_t iEnd2;    //!< the end offset of container 2 (mute element).
};

inline void LcsToDiff(const ArrayTraits<LcsItem>::ArrayType& arrLCS, int32_t n, int32_t m, ArrayTraits<DiffItem>::ArrayType& arrDiff)
{
	ArrayTraits<DiffItem>::Clear(arrDiff);
	if( n == 0 && m == 0 )
		return ;

	DiffItem ditem;
	ditem.iStart1 = 0;
	ditem.iStart2 = 0;
	if( n == 0 ) {
		ditem.iType = Diff_Add;
		ditem.iEnd1 = 0;
		ditem.iEnd2 = m - 1;
		ArrayTraits<DiffItem>::Append(ditem, arrDiff);  //may throw
		return ;
	}
	if( m == 0 ) {
		ditem.iType = Diff_Delete;
		ditem.iEnd1 = n - 1;
		ditem.iEnd2 = 0;
		ArrayTraits<DiffItem>::Append(ditem, arrDiff);  //may throw
		return ;
	}
	uintptr_t lcs_size = ArrayTraits<LcsItem>::GetSize(arrLCS);
	if( lcs_size == 0 ) {
		ditem.iType = Diff_Revise;
		ditem.iEnd1 = n - 1;
		ditem.iEnd2 = m - 1;
		ArrayTraits<DiffItem>::Append(ditem, arrDiff);  //may throw
		return ;
	}

	//loop
	int32_t iLast1 = -1;
	int32_t iLast2 = -1;
	for( uintptr_t i = 0; i < lcs_size; i ++ ) {
		const LcsItem& sitem(ArrayTraits<LcsItem>::GetAt(arrLCS, i));
		ditem.iStart1 = iLast1 + 1;
		ditem.iStart2 = iLast2 + 1;
		if( sitem.iStart1 == iLast1 + 1 ) {
			if( (i == 0 && sitem.iStart2 != 0) || i != 0 ) {
				assert( (i == 0) || (sitem.iStart2 != iLast2 + 1) );
				ditem.iType = Diff_Add;
				ditem.iEnd1 = iLast1 + 1;
				ditem.iEnd2 = sitem.iStart2 - 1;
				ArrayTraits<DiffItem>::Append(ditem, arrDiff);  //may throw
			}
		}
		else {
			if( sitem.iStart2 == iLast2 + 1 ) {
				ditem.iType = Diff_Delete;
				ditem.iEnd1 = sitem.iStart1 - 1;
				ditem.iEnd2 = iLast2 + 1;
				ArrayTraits<DiffItem>::Append(ditem, arrDiff);  //may throw
			}
			else {
				ditem.iType = Diff_Revise;
				ditem.iEnd1 = sitem.iStart1 - 1;
				ditem.iEnd2 = sitem.iStart2 - 1;
				ArrayTraits<DiffItem>::Append(ditem, arrDiff);  //may throw
			}
		}
		iLast1 = sitem.iEnd1;
		iLast2 = sitem.iEnd2;
	}
	//tail
	ditem.iStart1 = iLast1 + 1;
	ditem.iStart2 = iLast2 + 1;
	if( iLast1 == n - 1 ) {
		if( iLast2 < m - 1 ) {
			ditem.iType = Diff_Add;
			ditem.iEnd1 = iLast1 + 1;
			ditem.iEnd2 = m - 1;
			ArrayTraits<DiffItem>::Append(ditem, arrDiff);  //may throw
		}
	}
	else {
		if( iLast2 == m - 1 ) {
			ditem.iType = Diff_Delete;
			ditem.iEnd1 = n - 1;
			ditem.iEnd2 = iLast2 + 1;
			ArrayTraits<DiffItem>::Append(ditem, arrDiff);  //may throw
		}
		else {
			ditem.iType = Diff_Revise;
			ditem.iEnd1 = n - 1;
			ditem.iEnd2 = m - 1;
			ArrayTraits<DiffItem>::Append(ditem, arrDiff);  //may throw
		}
	}
}

////////////////////////////////////////////////////////////////////////////////
}
////////////////////////////////////////////////////////////////////////////////
#endif
////////////////////////////////////////////////////////////////////////////////
